#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,mod=111121;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-48,ch=getchar();}
	return x*f;
}
int n,a[N];
vector<int> e[N];

inline int ksm(int x,int y){
	if(x==0) return 0;
	int res=1;
	while(y){
		if(y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
int fa[N],dep[N];
void dfs(int u,int f){
	fa[u]=f,dep[u]=dep[f]+1;
	for(int v:e[u])
		if(v!=f) dfs(v,u);
}

int ans;
inline int sol(int x,int y){
	int s1=a[x]&a[y],s2=a[x]|a[y];
	while(x^y){
		if(dep[x]<dep[y]) swap(x,y);
		x=fa[x],s1&=a[x],s2|=a[x];
	}
	return ksm(s1,s2);
}

signed main(){
	freopen("abstract.in","r",stdin);
	freopen("abstract.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int u,v,i=1;i<n;i++){
		u=read(),v=read();
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			ans=(ans+sol(i,j))%mod;
	cout<<ans;
	return 0;
}